#include "Ejercicio2.h"

/***********************************eje**************************************/

Ejercicio2::eje::eje()
{
    origen = 0;
    destino = 0;
}

Ejercicio2::eje& Ejercicio2::eje::operator=( const eje & otra )
{
    origen = otra.origen;
    destino = otra.destino;
    return *this;
}

/***********************************Tupla**************************************/

Ejercicio2::Tupla::Tupla()
{
    terminaEni = false;
    terminaEnj = false;
}

Ejercicio2::Tupla& Ejercicio2::Tupla::operator=( const Tupla & otra )
{
    terminaEni = otra.terminaEni;
    terminaEnj = otra.terminaEnj;
    return *this;
}

/******************************************************************************/

Ejercicio2::Ejercicio2()
{
}

Ejercicio2::~Ejercicio2()
{
}

void Ejercicio2::execute( const string& in, const string& out ) const
{
	ifstream fin( in.c_str(), ios::in );
	ofstream fout( out.c_str(), ios::out );
	
	if( fin.good() && fout.good() )
	{
        stringstream ss;
		string linea = "", salida = "";
		int pueblos = 0, acuerdos = 0, p1, p2;
		unsigned int i, j;
		list<int> res;
		
		//por cada caso
		while( getline( fin, linea ) && linea != "0 0" )
		{
            j = 0;
			
			 while( j < linea.length() && linea[j] != ' ' )
			 	j++;
			 	
			pueblos = atoi( linea.substr( 0, j ).c_str() );
			acuerdos = atoi( linea.substr( j+1, linea.length() ).c_str() );
			
			Ejercicio2::eje ejes[ acuerdos ];
			
			for( int i = 0; i < acuerdos && getline( fin, linea ) && linea != "0 0"; i++ )
    		{	
                j = 0;
    		
    			 while( j < linea.length() && linea[j] != ' ' )
    			 	j++;
    		 	
                ejes[i].origen = atoi( linea.substr( 0, j ).c_str() );
                ejes[i].destino = atoi( linea.substr( j+1, linea.length() ).c_str() );
    		}
    		
    		res = rutaComercial( pueblos, acuerdos, ejes );
    		
    		if( salida != "" )
                salida+= "\n";
    		
    		for( list<int>::iterator it = res.begin(); it != res.end(); it++ )
    		{
                if( it != res.begin() )
                    salida+= " ";
                    
    			ss.str("");
    			ss << *it;
    			salida+= ss.str();
            }
        }
        
        fout.write( salida.c_str(), salida.length() );
	}
	
	if( fin.good() )
		fin.close();
	if( fout.good() )
		fout.close();
}

list<int> Ejercicio2::rutaComercial( int pueblos, int acuerdos, Ejercicio2::eje ejes[] ) const
{
    //resultado
    list<int> res;
    
    //cotadores
    unsigned int i, j;
    
    //matriz de adyacencia
    bool **M = new bool*[pueblos];
			
	//inicializo la matriz de adyacencia
	for( i = 0; i < pueblos; i++ )
	{
		M[i] = new bool[pueblos];

		for( j = 0; j < pueblos; j++ )
		{
			M[i][j] = false;
		}
	}
	
	//completo los datos de la matriz de adyacencia
	Ejercicio2::eje e;
	
	for( i = 0; i < acuerdos; i++ )
	{
        e = ejes[i];
        
    	M[e.origen-1][e.destino-1] = true;
    	M[e.destino-1][e.origen-1] = true;
    }

    //orden del camino
	int camino[pueblos];
	
	//me fijo si hay un camino
	if( hayCamino( M, pueblos, camino ) )
	{
        //recorro el orden del camino
	 	for( i = 0; i < pueblos; i++ )
	 	{
            res.push_back( camino[i] );
		}
	}
	//si no hay camino
	else
	{
        res.push_back(-1);
	}

    //libero cada columna de la matriz
	for( i = 0; i < pueblos; i++ )
	{
		if( M[i] != NULL )
    		delete M[i];
	}

    //libero las filas de la matriz
	delete[] M;
	
	return res;
}

bool Ejercicio2::hayCamino( bool **m, int n, int camino[] ) const
{
	int i,j,k,abajo,izq = 0;
	
	//armo una matriz de tuplas
    Tupla **T = new Tupla*[n];
    
	for( i = 0; i < n; i++ )
	{
		T[i] = new Tupla[n];
 	}

    for( i = 0; i < n; i++ )
    {
        j = ( ( i + 1 )  % n );
        /*para los i,i+1 mod(n) es lo mismo que preguntar si 
        existe un camino directo entre i y j y ademas sabemos que 
        termina en ambas ciudades*/
        if( m[i][j] )
        {
            T[i][j].terminaEni = true;
            T[i][j].terminaEnj = true;   
        }
        else
        {
            T[i][j].terminaEni = false;
            T[i][j].terminaEnj = false;			
		}  
    }
    
    for(k = 2; k < n; k++)
    {
        for( i = 0; i < n; i++ )
        {
            //i se define de esta forma para recorrer la matriz en diagonal
            j = ( ( i + k ) % n );
            
            if( j <= 0 )
            {
                izq = j - 1 + n;
            }
            else
            {
                izq = j - 1;         
            }
            
            abajo = ( ( i + 1 ) % n );

	       T[i][j].terminaEni = (m[i][abajo] && T[abajo][j].terminaEni) || (m[i][j] && T[abajo][j].terminaEnj); 
	       T[i][j].terminaEnj = (m[j][izq] && T[i][izq].terminaEnj) ||(m[i][j] && T[i][izq].terminaEni);
        }
    }
    
    bool solucion = false;
    
    //chequea si hay una solucion
    for(j = 0; j < n; j++)
    {
        i = ( ( j + 1 ) % n );
        solucion = solucion || ( T[i][j].terminaEni || T[i][j].terminaEnj );
    }

    //si hay solucion genero el camino
    //queda guardado en el arreglo 'camino'
    if(solucion)
		generarCamino( m, T, n, camino );
    
    //libero cada columna de la matriz de tuplas
	for( i = 0; i < n; i++ )
	{
		delete T[i];
	}
	
	//libero cada fila de la matriz de tuplas
	delete[] T;
     
    //indico si hay solucion
	return solucion;
}

void Ejercicio2::generarCamino(bool **m, Tupla** T, int n, int camino[] ) const
{
 	 int i,j,k,ant,sig;
 	 i = j = k = ant = sig = 0;
 	 bool ti;

	 for( i = 0; i < n; i++ )
	 {
        camino[k] = 0;
     }
     
	 for(j = 0; j < n; j++)
	 {
	 		i = ( ( j + 1 ) % n );
	 		if(T[i][j].terminaEni || T[i][j].terminaEnj)
	 		{
                 break;    
	 		}         
	 }
	 
	 ti=T[i][j].terminaEni;
	 
	 for(k = 0; k < n; k++)
	 {
           if(T[i][j].terminaEni && T[i][j].terminaEnj)
           {
                if( ( ( (j - i) == 1 ) || (i == n-1 && j == 0)) && ti ) 
                {
                    camino[k] = i + 1;
                    k++;
                    camino[k] = j + 1;    
                }
                else if( ( ((j - i) == 1) || (i == n-1 && j == 0) ) )
                {
                    camino[k] = j + 1;
                    k++;
                    camino[k] = i + 1;                          
                }
			    else if(ti)
			    {
	                if(j - i == 1)
	                {
	                    camino[k] = j + 1;
	                    k++;
	                    camino[k] = i + 1;    
	                } 
	                else
	                {
	                    sig = (i + 1)% n;
	                    
	                    if( ( m[i][sig] ) && (T[sig][j].terminaEni) )
	                    {
	                        camino[k] = i+1;
	                        i = sig;  
	                        ti = true;  
	                    }
	                    else if( (m[i][j]) && (T[sig][j].terminaEnj) )
	                    {
	                         camino[k] = i+1;
	                         i = sig; 
	                         ti = false;  
	                    }        
	                } 
                }
                else
                {
	                if(j - i == 1)
	                {
	                    camino[k] = i + 1;
	                    k++;
	                    camino[k] = j + 1;    
	                } 
	                else
	                {
	                    if( j <= 0 )
	                    {
	                        ant = ( j - 1 + n );
	                    }
	                    else
	                    {
	                        ant = j - 1;     
	                    }
	                    if( ( m[ant][j] ) && (T[i][ant].terminaEnj) )
	                    {
	                        camino[k] = j + 1;
	                        j = ant;  
	                        ti=false;  
	                    }
	                    else if( (m[i][j]) && (T[i][ant].terminaEni) )
	                    {
	                         camino[k] = j + 1;
	                         j = ant;
	                         ti=true;   
	                    }        
	                }             
                }
          }
	       else if(T[i][j].terminaEni)
	       {
                sig = (i + 1)% n;
                
                if( ( m[i][sig] ) && (T[sig][j].terminaEni) )
                {
                    camino[k] = i+1;
                    i = sig;  
                    ti = true;  
                }
                else if( (m[i][j]) && (T[sig][j].terminaEnj) )
                {
                     camino[k] = i+1;
                     i = sig; 
                     ti = false;  
                }
           }
           else if(T[i][j].terminaEnj)
           {
                if( j <= 0 )
                {
                    ant = ( j - 1 + n );
                }
                else
                {
                    ant = j - 1;     
                }
                
                if( ( m[ant][j] ) && (T[i][ant].terminaEnj) )
                {
                    camino[k] = j + 1;
                    j = ant;  
                    ti=false;  
                }
                else if( (m[i][j]) && (T[i][ant].terminaEni) )
                {
                     camino[k] = j + 1;
                     j = ant;
                     ti=true;   
                }        
           }
     }  
}
